#https://zhuanlan.zhihu.com/p/38628604

def merge_sort(a_list):
    if len(a_list) > 1:
        mid = len(a_list)//2
        left_half = a_list[:mid]
        right_half = a_list[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = 0
        j = 0
        k = 0
        while i<len(left_half) and j<len(right_half):
            if left_half[i]<=right_half[j]:
                a_list[k] = left_half[i]
                i +=1
            else:
                a_list[k] = right_half[j]
                j +=1
            k +=1

        while i<len(left_half):
            a_list[k] = left_half[i]
            i += 1
            k +=1
        
        while j<len(right_half):
            a_list[k] = right_half[j]
            j +=1
            k +=1    

    return a_list

if __name__ == "__main__":
    a_list = [3,6,4,1,2,9,2]
    sorted_list = merge_sort(a_list) 
    print(sorted_list)    
    pass
